/*!
 * \file AUnicite.c
 * \author Catalin BLAJ
 * \date 30 Octobre 2013
 *
 * Fichier source AUnicite.c pour le programme du Sudoku
 */


#include "AUniciteGrille.h"

bool UG_miseAJourCandidat(SGrille* grille, SCase* maCase)
{
	unsigned char type = SG_getType(grille);
	unsigned nombreUnites = pow(type, 2);

	/* Vérification des paramètres */
	assert(grille != NULL);
    assert(maCase != NULL);

    /* On parcourt la ligne */
    unsigned short indiceLigne = SC_getIndice(maCase)/nombreUnites;
    for (unsigned i=0; i<nombreUnites; i++)
    {
        if (SC_getEtat(SU_getCase(SG_getLigne(grille, indiceLigne), i)) != vide)
            SC_retirerCandidat(maCase, SC_getValeur(SU_getCase(SG_getLigne(grille, indiceLigne), i)));
    }

    /* On parcourt la colonne */
    unsigned short indiceColonne = SC_getIndice(maCase)%nombreUnites;
    for (unsigned i=0; i<nombreUnites; i++)
    {
        if (SC_getEtat(SU_getCase(SG_getColonne(grille, indiceColonne), i)) != vide)
            SC_retirerCandidat(maCase, SC_getValeur(SU_getCase(SG_getColonne(grille, indiceColonne), i)));
    }

    /* On récupère l'indice de la région d'une case */
    unsigned short indiceRegion = type*(indiceLigne/type) + indiceColonne/type;
    for (unsigned i=0; i<nombreUnites; i++)
    {
        if (SC_getEtat(SU_getCase(SG_getRegion(grille, indiceRegion), i)) != vide)
            SC_retirerCandidat(maCase, SC_getValeur(SU_getCase(SG_getRegion(grille, indiceRegion), i)));
    }

	return (SC_getNombreCandidats(maCase) != 0);
}


/**
 * \brief Traite la grille dans la fonction de résolution.
 * \param grille : Grille à resoudre (donnée-résultat).
 * \param maCase : Pointeur de case qui pointera sur la case possédant le moins de candidats si la grille n'est pas résolue (donnée-résultat).
 * \return Renvoie vrai si la grille est complète, faux si elle ne l'est pas.
 *
 * Cette fonction effectue un traitement de la grille a résoudre et retourne l'avancement de la grille.
 */
static int UG_traitementGrille(SGrille* grille, SCase** maCase)
{
    /* Variables de convenance */
    unsigned char type = SG_getType(grille);
    unsigned char nombreMinCandidats = type*type;
    unsigned int nombreCases = type*type*type*type;

    /* Vérification des paramètres */
    assert (grille != NULL);

    /* Pour chaque case qui est vide on met a jour les candidats */
    bool fini = true;
    for (unsigned i=0; i<nombreCases; i++)
    {
        if (SC_getEtat(SG_getCase(grille,i)) == vide)
        {
            fini = false;
            if (!UG_miseAJourCandidat(grille, SG_getCase(grille,i)))
                return -1; /* On renvoie -1 pour signifier qu'il n'y a pas de solution pour cette grille, car une case n'a plus aucun candidat */
        }
    }

    /* Et on cherche la case qui possede le moins de candidats (si la grille n'est pas terminée */
    if (!fini)
    {
        /* On cherche la case possédant le moins de candidats et on la met dans maCase */
        for(unsigned i=0; i<nombreCases; i++)
        {
            if (SC_getEtat(SG_getCase(grille, i)) == vide)
            {
                if (SC_getNombreCandidats(SG_getCase(grille, i)) < nombreMinCandidats)
                {
                    nombreMinCandidats = SC_getNombreCandidats(SG_getCase(grille, i));
                    *maCase = SG_getCase(grille, i);
                }
            }
        }
    }

    return fini;
}


int UG_resolution(SGrille* grille)
{
    /* Variables de convenances */
	unsigned char type = SG_getType(grille);
	unsigned short nombreCandidats = type*type;

    /* Vérification des paramètres */
    assert(grille != NULL);

    /* On résout la grille avec la technique des singletons nus */
    RL_resoudreGrille(grille);

    /* Une case vierge qui nous permettra de tester les possibilités de résolution du Sudoku (on résout en interne le Sudoku en mettant des valeurs ici et là) */
    SCase* maCase = NULL;
    int nombreSolutions = 0;

    /* On traite la grille, on teste si elle est pleine (=> renvoie 1), si impossible à résoudre (=> renvoie 0). Sinon on recupere la case a traiter dans scase */
    switch(UG_traitementGrille(grille, &maCase))
    {
        case 1:
            return 1; /* La grille est complete et terminer */
            break;
        case -1:
            return 0; /* La grille est insolvable */
            break;
        default:
            break; /* Resolution en cours */
    }

    /* On met une valeur dans cette case */
    for (unsigned i=0; i<nombreCandidats; i++)
    {
        if (SC_getCandidat(maCase, i))
        {
            SC_setValeur(maCase, i);
            SC_setEtat(maCase, valide);
            SC_setCandidats(maCase, pow2(i));

            /* On tente de résoudre à nouveau la grille récursivement. Si on y arrive, on incrémente le compteur de solutions */
            if (UG_resolution(grille))
                nombreSolutions++;
        }
    }

    /* Si le compteur n'est pas monté (pas de solutions), on revide la case et on renvoit 0 (pour les étages supérieurs), sinon on renvoit le nombre de solutions */
    if (!nombreSolutions)
    {
        SC_setEtat(maCase, vide);
        SC_setValeur(maCase, -1);
    }

    /* On renvoie le nombre de solutions */
    return nombreSolutions;
}
